题目 T46746.【贪心算法(一)】最优装载问题 T46747.【贪心算法(一)】粮草 T46745.【贪心算法(一)】接水问题二 T46748.【贪心算法(一)】骑士的工作 T46775.【贪心算法(二)】分发饼干 T46777.【贪心算法(二)】游玩 T46776.【贪心算法(二)】活动安排
T46746.【贪心算法(一)】最优装载问题
题目大意
一艘海盗船的最大载重量为 C,海盗们截获了一批古董,共有 n 件,每件古董的重量为 w_i。海盗们希望在不超过最大载重的前提下,尽可能多地将古董装船。你的任务是计算最多能装多少件古董。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题是典型的背包问题的贪心变形。我们不关注物品的总价值,只关心装得下尽量多的物品。由于没有价值限制,因此我们优先选择重量小的物品装入,从而可以装得更多。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
采用贪心策略:
* 将所有古董按重量从小到大排序;
* 然后按顺序依次尝试将古董装入船中;
* 如果当前古董能装入(累计重量未超标),则继续;
* 一旦不能装入,说明后面的更重物品也不能装,直接停止。
这是典型的“局部最优 => 全局最优”的贪心场景。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序耗时 O(n log n)
* 遍历一次 O(n)
* 总时间复杂度为 O(n log n),在 n ≤ 1000 的范围内运行良好。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46747.【贪心算法(一)】粮草
题目大意
有若干农户,每人给出了一种价格和能提供的最大粮草量。商会需要采购总量为 n 的粮草。
目标是从这些农户中购买足够数量的粮草,使总花费最小。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 每个农户提供 (单价, 数量) 的信息。
* 商会可以从任意农户购买任意量(不超过其最大值)。
* 要求商会总共采购到 不少于 n 单位 的粮草。
* 输出最少的总采购花费。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
这是典型的贪心策略问题,目标是用最少的钱买到足够的粮草。
贪心策略:优先从单价最低的农户那里购买粮草。
步骤如下:
1. 读取所有农户信息(单价、数量)。
2. 按照单价 p_i 从小到大排序。
3. 从价格最便宜的农户开始购买粮草:
* 如果当前农户能满足所有剩余需求,就只买需要的部分。
* 否则把该农户所有粮草买完,然后继续从下一个便宜的农户买。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序:O(m log m),其中 m 是农户数量。
* 遍历农户:O(m)
* 总体复杂度:O(m log m),在 m ≤ 5000 的范围内表现良好。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46745.【贪心算法(一)】接水问题二
一、题目大意
给定 n 个人,每个人接水所需时间为 T_i,只能一个人一个人依次接水。现在要安排这 n 个人的接水顺序,使得 所有人平均等待时间最小。输出该顺序中每个人的原始编号,并输出最小平均等待时间(保留两位小数)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、题意分析
* 每个人的等待时间 = 前面所有人接水时间之和。
* 总等待时间 = 所有人的等待时间加总。
* 平均等待时间 = 总等待时间 / n
要想平均等待时间最小,就要让耗时短的人排在前面,减少其接水时间对后续人员的影响。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、解题思路
贪心策略:
我们从另一个角度看问题:
第 i 个人接水的时间是 a[i],他会让后面 n - i 个人都等待 a[i] 时间。
因此:
* 每个人的接水时间对总等待时间的贡献是:a[i] * (n - i)
* 要让总等待时间最小,就让 a[i] 越小的人越早排。
实现步骤:
1. 将每个人的接水时间和原始编号一起读入;
2. 按接水时间升序排序;
3. 遍历每个人,累加其对总等待时间的贡献;
4. 输出排序后的编号序列;
5. 计算并输出平均等待时间。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、时间复杂度分析
* 排序时间复杂度:O(n log n)
* 遍历计算总等待时间:O(n)
* 总体复杂度为:O(n log n),在 n <= 1000 范围内可以轻松通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、代码演示
T46748.【贪心算法(一)】骑士的工作
题目大意
一条恶龙有 n 个头,每个头有一个大小。你需要找来一些骑士来砍掉这些头。共有 m 位骑士,每个骑士只能砍掉一个大小不超过他能力值的头,且出战需要支付与能力值相同的金币数。你需要选择若干骑士,让他们砍掉所有龙头,且总花费最少。如果无法砍完所有龙头,输出 "you died!"。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 每个龙头只能被一个骑士砍掉;
* 每位骑士只能砍一个头,不能重复使用;
* 骑士的能力值即为费用,能力越强,花费越高;
* 目标是完成全部龙头的砍杀任务,并使总金币花费最少。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
我们采用贪心算法来解决这个问题。
1. 将所有龙头按大小升序排列;
2. 将所有骑士按能力值升序排列;
3. 对于每一个龙头,从前往后找能力值刚好或刚好大于它的最便宜的骑士;
4. 找到合适的骑士后安排出战,记录花费,并同时跳过该骑士;
5. 如果某个龙头找不到骑士能砍掉,直接输出 "you died!"。
这种贪心策略是可行的,因为:
* 较小的龙头优先被能力值低的骑士砍掉,节省费用;
* 强力骑士保留给更大的龙头使用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序耗时 O(n log n + m log m)
* 遍历两个数组进行匹配 O(n + m)
* 总时间复杂度为 O(n log n),在 n, m ≤ 20000 的范围内运行良好。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46775.【贪心算法(二)】分发饼干
题目大意
有 n 盒大小不同的饼干,要分给 m 个孩子。每个孩子有一个“期望的饼干大小”,只有当饼干大小 ≥ 他的期望值时,他才会满意。每个孩子最多只能得到一盒饼干,问最多有多少个孩子可以获得满足。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 每个孩子最多只能分到一盒饼干;
* 一盒饼干也只能分给一个孩子;
* 饼干的大小必须 大于等于 孩子的期望值才能使他满意;
* 要使尽可能多的孩子满意。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
采用 贪心策略:
1. 将所有饼干大小从小到大排序;
2. 将所有孩子的期望值从小到大排序;
3. 用双指针 i 和 j 分别指向当前考虑的饼干和孩子:
* 如果当前饼干可以满足当前孩子,则分配它,两个指针都后移;
* 否则说明饼干太小,只能尝试下一块更大的饼干;
4. 重复直到饼干或孩子遍历完。
贪心的核心思路是:
> 小的饼干优先满足小的需求,避免“大饼干喂小孩”造成浪费。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序饼干数组:O(n log n)
* 排序孩子需求数组:O(m log m)
* 双指针遍历:O(n + m)
* 总体时间复杂度为 O(n log n + m log m),在 n, m ≤ 10000 的范围内表现良好。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46777.【贪心算法(二)】游玩
题目大意
有 n 个人出海游玩,每艘船最多能承载两个人,且总重量不能超过 m。每个人有一个固定的体重。现在希望用最少数量的船把所有人都送出去,求最小的船只数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 每艘船最多坐两人;
* 两人的总重量不能超过 m;
* 每人必须上船,不能遗漏;
* 要求使用最少数量的船。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
采用 贪心策略 + 双指针:
1. 将所有人的体重从小到大排序;
2. 用两个指针 i(最轻的人)和 j(最重的人);
3. 每次尝试将最轻和最重的人配对上船:
* 如果他们的体重之和不超过最大载重 m,则配对成功,i++, j--;
* 否则,只能让重的人单独上船,j--;
4. 每次操作代表一艘船,计数器 sum++;
5. 循环直到所有人都分配完。
贪心思想是:
> 用最重的人尽量去“搭配”最轻的人,节省船只数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序体重数组:O(n log n)
* 双指针遍历:O(n)
* 总体时间复杂度:O(n log n),对于 n ≤ 1000 表现良好。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
T46776.【贪心算法(二)】活动安排
题目大意
给定 n 个活动,每个活动有一个开始时间 s 和结束时间 e。如果一个活动的开始时间大于等于另一个活动的结束时间,那么可以连续参加这两个活动。
问:最多可以参加多少个互不重叠的活动?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 每个活动只能选择一次;
* 活动时间不能重叠;
* 可以选的活动顺序不固定;
* 目标是选择尽可能多的活动。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
采用 贪心策略(按照结束时间排序):
1. 将所有活动按照结束时间升序排序;
2. 每次选择当前结束时间最早,且不与已选活动冲突(开始时间 ≥ 上一个活动的结束时间)的活动;
3. 更新当前的时间 now = 当前活动的结束时间,统计可选的活动数量。
贪心的核心思想是:
> 优先安排结束早的活动,为后续活动留出更多空间,最大化可选数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
* 排序活动数组:O(n log n)
* 遍历判断可选活动:O(n)
* 总体时间复杂度为 O(n log n),在 n ≤ 1000 范围内可以高效运行。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示